package io.tec.cloud.algorithm.c15_v20220711;

import java.util.*;

/**
 * 84	15_2	15	2	15并查集及其面试题目	岛屿数量|岛问题
 * 200. Number of Islands
 * Medium
 * <p>
 * Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
 * <p>
 * An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
 * <p>
 * https://leetcode.com/problems/number-of-islands/
 */
public class Code15_2_NumberOfIslands {

    public static void main(String[] args) {
        char[][] arr = {{'1','1','1','1','1','0','1','1','1','1'},{'1','0','1','0','1','1','1','1','1','1'},{'0','1','1','1','0','1','1','1','1','1'},{'1','1','0','1','1','0','0','0','0','1'},{'1','0','1','0','1','0','0','1','0','1'},{'1','0','0','1','1','1','0','1','0','0'},{'0','0','1','0','0','1','1','1','1','0'},{'1','0','1','1','1','0','0','1','1','1'},{'1','1','1','1','1','1','1','1','0','1'},{'1','0','1','1','1','1','1','1','1','0'}};
        System.out.println(numIslands(arr));
    }

    public static int numIslands(char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;

        Dot[][] board = new Dot[row][col];
        List<Dot> dotList = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    Dot dot = new Dot();
                    board[i][j] = dot;
                    dotList.add(dot);
                }
            }
        }
        UnionFind unionFind = new UnionFind(dotList);

        for (int i = 1; i < row; i++) {
            if (grid[i - 1][0] == '1' && grid[i][0] == '1') {
                unionFind.union(board[i - 1][0], board[i][0]);
            }
        }


        for (int j = 1; j < col; j++) {
            if (grid[0][j - 1] == '1' && grid[0][j] == '1') {
                unionFind.union(board[0][j - 1], board[0][j]);
            }
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (grid[i - 1][j] == '1' && grid[i][j] == '1') {
                    unionFind.union(board[i - 1][j], board[i][j]);
                }

                if (grid[i][j - 1] == '1' && grid[i][j] == '1') {
                    unionFind.union(board[i][j - 1], board[i][j]);
                }
            }
        }


        return unionFind.sets();
    }

    static class Dot {

    }

    static class Node<T> {
        T v;

        Node(T value) {
            v = value;
        }
    }

    static class UnionFind<T> {
        HashMap<T, Node<T>> nodeMap;
        HashMap<Node<T>, Node<T>> parentMap;
        HashMap<Node<T>, Integer> sizeMap;

        UnionFind(List<T> list) {
            nodeMap = new HashMap<>();
            parentMap = new HashMap<>();
            sizeMap = new HashMap<>();
            for (T v : list) {
                Node<T> cur = new Node<>(v);
                nodeMap.put(v, cur);
                parentMap.put(cur, cur);
                sizeMap.put(cur, 1);
            }
        }

        public void union(T a, T b) {
            final Node<T> aParent = findFather(nodeMap.get(a));
            final Node<T> bParent = findFather(nodeMap.get(b));
            if (aParent != bParent) {
                Integer aSize = sizeMap.get(aParent);
                Integer bSize = sizeMap.get(bParent);
                Node<T> more = aSize > bSize ? aParent : bParent;
                Node<T> less = more == aParent ? bParent : aParent;
                parentMap.put(less, more);
                sizeMap.put(more, aSize + bSize);
                sizeMap.remove(less);
            }
        }

        private Node<T> findFather(Node<T> tNode) {
            Stack<Node> path = new Stack<>();
            // TODO while 不是if
            while (tNode != parentMap.get(tNode)) {
                path.push(tNode);
                tNode = parentMap.get(tNode);
            }
            while (!path.isEmpty()) {
                parentMap.put(path.pop(), tNode);
            }
            return tNode;
        }

        public Integer sets() {
            return sizeMap.size();
        }


    }
}